class Tree:
    def __init__(self, val):
        self.val = val
        self.neighbors = {}
        self.count = 0


import collections
class Solution(object):
    def maxGeneticDifference(self, parents, queries):
        m = 15
        root = Tree(-1)
        d = collections.defaultdict(set)
        for index, num in enumerate(parents):
            if num == -1:
                start = index
            else:
                d[num].add(index)
        def dfs(u):
            node = root
            for i in range(m - 1, -1, -1):
                val = (u >> i) & 1
                if val in node.neighbors:
                    node = node.neighbors[val]
                else:
                    new_node = Tree(val)
                    node.neighbors[val] = new_node
                    node = new_node
                node.count += 1        
            for v in d_query[u]:
                node = root
                out = 0
                for i in range(m - 1, -1, -1):
                    v_val = (v >> i) & 1
                    if 1 - v_val in node.neighbors:
                        node = node.neighbors[1 - v_val]
                        out |= (1 << i)
                    else:
                        node = node.neighbors[v_val]
                for index in d_index[(u, v)]:
                    ans[index] = out
            for v in d[u]:
                dfs(v)
            prev_node = root
            node = root
            for i in range(m - 1, -1, -1):
                val = (u >> i) & 1
                node = node.neighbors[val]
                node.count -= 1
                if node.count == 0:
                    prev_node.neighbors.pop(val)
                    break
                else:
                    prev_node = node
               
        d_query = collections.defaultdict(set)
        d_index = collections.defaultdict(set)
        ans = [0] * (len(queries))
        for index, (u, v) in enumerate(queries):
            d_query[u].add(v)
            d_index[(u, v)].add(index) 

        dfs(start)

        return ans

        





data = Solution()
# parents = [-1,0,1,1]
# queries = [[0,2],[3,2],[2,5]]
# print(data.maxGeneticDifference(parents, queries))
parents = [6,2,9,7,9,6,8,-1,9,7]
queries = [[2,37],[4,2], [9,32],[1,24],[9,12],[4,2],[6,0]]
print(data.maxGeneticDifference(parents, queries))